一、題目介紹
今天要解的題目是LeetCode的Maximum Subarray

題目會給我們一個整數陣列nums，要求找出其中一個連續子陣列（subarray），使它的元素總和最大，最後回傳這個最大總和。

例如：nums = [-2,1,-3,4,-1,2,1,-5,4]
其中[4,-1,2,1]的總和為：4 + (-1) + 2 + 1 = 6

因此答案為6
需要注意的是，這裡的子陣列必須是連續的，不能任意跳過中間元素來組合

二、解題思路
最直覺的方法是把所有可能的連續子陣列都找出來，再計算它們的總和
但是這樣需要大量的計算，效率並不好，因此這題可以使用Kadane's Algorithm
核心概念非常簡單：走訪陣列時，記錄「以目前元素結尾的最大子陣列總和」

我們使用兩個變數

• currentSum：代表目前這一段連續子陣列的最大總和
• maxSum：代表目前找到的最大子陣列總和

三、Kadane's Algorithm 的核心
假設目前遇到一個新的數字num
我們需要思考一件事情：要不要把新的數字接在目前的子陣列後面？
有兩種選擇，一種是currentSum + num或者乾脆num重新從目前這個數字開始
因此可以寫成currentSum = max(num, currentSum + num)
意思就是：如果繼續目前這段比較好，就繼續；如果重新開始比較好，就放棄前面的總和。
接著再更新maxSum = max(maxSum, currentSum)

四、實際範例
以以下為例
[-2,1,-3,4,-1,2,1,-5,4]
可以觀察currentSum如何變化

最後maxSum = 6，所以答案就是6，其中最大的連續子陣列就是[4,-1,2,1]

五、Java實作

六、Python實作

七、為什麼不需要記錄整個子陣列？
這是這題我覺得最值得理解的地方

我們真正需要的答案是最大總和
所以在計算過程中，不需要把每一個可能的子陣列全部保存下來
只要知道「以目前位置結尾，最好的總和是多少？」就足夠了

例如目前currentSum = -2接著遇到4
如果繼續原本的子陣列-2 + 4 = 2
但如果直接從4開始
顯然4 > 2
所以前面的負數就沒有必要繼續保留

這就是Kadane's Algorithm最重要的判斷：如果前面的累積結果只會拖累後面的總和，就重新開始。

八、時間與空間複雜度
這個演算法只需要將陣列走訪一次
因此時間複雜度為O(n)

不需要額外建立與陣列大小相關的資料結構
因此額外空間複雜度為O(1)

相較於暴力枚舉所有連續子陣列的方法，Kadane's Algorithm可以將問題有效率地降到線性時間

九、Java與Python解法比較

十、實作結果
Leetcode測試結果：Accepted

十一、今日學習心得
今天學習Maximum Subarray時，我第一次比較明顯地感受到動態地保留「有用資訊」的重要性。

如果使用暴力方法，需要不斷計算不同子陣列的總和，當資料量增加時，計算量也會跟著增加。

而Kadane's Algorithm不需要保存所有可能的子陣列，而是只記錄目前最有價值的資訊：以目前位置結尾的最大總和。

當前面的累積總和變成負數時，繼續保留它反而會降低後面的結果，因此可以直接重新開始。透過這樣的判斷，就能在一次走訪陣列的情況下找到答案。

今天最大的收穫是：解題時不一定要記住所有過程，只要保留對未來有用的資訊，就能讓演算法變得更加有效率。

這題也讓我了解到，Kadane's Algorithm的核心並不只是公式，而是「是否值得繼續累積」的判斷。